package org.chnxi.algorithm.greedy;

import java.util.*;

/**
 * 贪心算法-电台覆盖查找
 */
public class GreedyAlgorithm {

    public static void main(String[] args) {

        //组装电台与覆盖城市
        Map<String , Set<String>> broadcasts = new HashMap<>();

        Set<String> bc1 = new HashSet<>();
        broadcasts.put("K1" , bc1);
        bc1.add("北京");
        bc1.add("上海");
        bc1.add("天津");


        Set<String> bc2 = new HashSet<>();
        broadcasts.put("K2" , bc2);
        bc2.add("广州");
        bc2.add("北京");
        bc2.add("深圳");

        Set<String> bc3 = new HashSet<>();
        broadcasts.put("K3" , bc3);
        bc3.add("成都");
        bc3.add("上海");
        bc3.add("杭州");

        Set<String> bc4 = new HashSet<>();
        broadcasts.put("K4" , bc4);
        bc4.add("上海");
        bc4.add("天津");

        Set<String> bc5 = new HashSet<>();
        broadcasts.put("K5" , bc5);
        bc5.add("杭州");
        bc5.add("大连");

        //存放所有地区
        Set<String> allAreas = new HashSet<>();
        broadcasts.forEach((k ,v) -> v.forEach(area ->allAreas.add(area)));
        System.out.println("全部区域："+allAreas);

        //存放已选择的电台
        List<String> selected = new ArrayList<>();

        //定义一个临时的集合，在遍历过程中，存放遍历过程中覆盖的地区
        Set<String> tmp = new HashSet<>();

        //定义maxKey，保存在一次遍历过程中，能够覆盖最大区域的电台
        //如果maxKey不为空，加入到selected中
        String maxKey = null;
        //如果allAreas不为空，表示还有未覆盖的地区
        while(allAreas.size() != 0){
            maxKey = null; //将maxKey重置为null
            for(String k : broadcasts.keySet()){
                tmp.clear(); //清除上次循环中的tmp
                Set<String> areas = broadcasts.get(k);
                tmp.addAll(areas);
                tmp.retainAll(allAreas); //求出两个集合的交集，赋值给tmp
                if(tmp.size() > 0 && (maxKey == null || tmp.size() > broadcasts.get(maxKey).size())){
                    maxKey = k;
                }
            }

            //不为空，表示已经找到，同时将allAreas中的数据移除，否则死循环
            if(maxKey != null){
                selected.add(maxKey);
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }

        System.out.println("得到的结果：selected="+selected);

    }

}
